home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / text / hyper / ADtoHT2_0.lha / AVL.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-10  |  6.6 KB  |  304 lines
  1. #ifndef EXEC_TYPES_H
  2. #include <exec/types.h>
  3. #endif
  4.  
  5. /************************************************************************/
  6.  
  7. #include "AVL.h"
  8.  
  9. /************************************************************************/
  10.  
  11. static void
  12. Rotate_R (struct AVLTree *Tree, struct AVLNode *Node)
  13.  
  14. {
  15.   struct AVLNode *Left, *Right;
  16.   struct AVLNode *Parent;
  17.  
  18.   Left = Node->Left;
  19.   Right = Node->Right;
  20.   Parent = Node->Parent;
  21.   if (Parent)
  22.     {
  23.       if (Parent->Left == Node)
  24.     {
  25.       Parent->Left = Left;
  26.     }
  27.       else
  28.     {
  29.       Parent->Right = Left;
  30.     }
  31.     }
  32.   else
  33.     {
  34.       Tree->Root = Left;
  35.     }
  36.  
  37.   Left->Parent = Parent;
  38.  
  39.   if ((Node->Left = Left->Right))
  40.     Left->Right->Parent = Node;
  41.  
  42.   Left->Right = Node;
  43.   Node->Parent = Left;
  44. }
  45.  
  46. /************************************************************************/
  47.  
  48. static void
  49. Rotate_L (struct AVLTree *Tree, struct AVLNode *Node)
  50.  
  51. {
  52.   struct AVLNode *Left, *Right;
  53.   struct AVLNode *Parent;
  54.  
  55.   Left = Node->Left;
  56.   Right = Node->Right;
  57.   Parent = Node->Parent;
  58.   if (Parent)
  59.     {
  60.       if (Parent->Left == Node)
  61.     {
  62.       Parent->Left = Right;
  63.     }
  64.       else
  65.     {
  66.       Parent->Right = Right;
  67.     }
  68.     }
  69.   else
  70.     {
  71.       Tree->Root = Right;
  72.     }
  73.  
  74.   Right->Parent = Parent;
  75.  
  76.   if ((Node->Right = Right->Left))
  77.     Right->Left->Parent = Node;
  78.  
  79.   Right->Left = Node;
  80.   Node->Parent = Right;
  81. }
  82.  
  83. /************************************************************************/
  84. /*                                                                      */
  85. /* Insert a node into a tree.                                           */
  86. /* If a node with the same key already exists, return it.               */
  87. /* Return NULL if successfull.                                          */
  88. /*                                                                      */
  89. /************************************************************************/
  90.  
  91. struct AVLNode *
  92. AVL_InsertNode (struct AVLTree *Tree, struct AVLNode *Node)
  93.  
  94. {
  95.   struct AVLNode *CurrentNode, *Parent;
  96.   int CompareResult;    /* never used unitialized */
  97.  
  98.   /* Step 1: Find place where to insert node */
  99.   CurrentNode = Tree->Root;
  100.   Parent = NULL;
  101.   while (CurrentNode)
  102.     {
  103.       Parent = CurrentNode;
  104.       CompareResult = Tree->CompareNodes (CurrentNode, Node);
  105.       if (CompareResult > 0)
  106.     {
  107.       CurrentNode = CurrentNode->Left;
  108.     }
  109.       else if (CompareResult < 0)
  110.     {
  111.       CurrentNode = CurrentNode->Right;
  112.     }
  113.       else
  114.     {
  115.       return CurrentNode;
  116.     }
  117.     }
  118.  
  119.   /* Step 2: Link node into tree */
  120.   Node->Left = Node->Right = NULL;
  121.   Node->Balance = 0;
  122.   Node->Parent = Parent;
  123.   if (Parent)
  124.     {
  125.       if (CompareResult > 0)
  126.     {
  127.       Parent->Left = Node;
  128.     }
  129.       else
  130.     {
  131.       Parent->Right = Node;
  132.     }
  133.     }
  134.   else
  135.     {
  136.       Tree->Root = Node;
  137.     }
  138.  
  139.   /* Step 3: Balance tree */
  140.   while (Parent)
  141.     {
  142.       if (Parent->Left == Node)
  143.     {
  144.       switch (Parent->Balance)
  145.         {
  146.         case -1:
  147.           if (Node->Balance == -1)
  148.         {
  149.           Parent->Balance = 0;
  150.           Node->Balance = 0;
  151.         }
  152.           else
  153.         {
  154.           Parent->Balance = (Node->Right->Balance == -1);
  155.           Node->Balance = -(Node->Right->Balance == 1);
  156.           Node->Right->Balance = 0;
  157.           Rotate_L (Tree, Node);
  158.         }
  159.           Rotate_R (Tree, Parent);
  160.           return NULL;
  161.  
  162.         case 0:
  163.           Parent->Balance = -1;
  164.           Node = Parent;
  165.           Parent = Node->Parent;
  166.           break;
  167.  
  168.         case +1:
  169.           Parent->Balance = 0;
  170.           return NULL;
  171.         }
  172.     }
  173.       else
  174.     {
  175.       switch (Parent->Balance)
  176.         {
  177.         case -1:
  178.           Parent->Balance = 0;
  179.           return NULL;
  180.  
  181.         case 0:
  182.           Parent->Balance = 1;
  183.           Node = Parent;
  184.           Parent = Node->Parent;
  185.           break;
  186.  
  187.         case +1:
  188.           if (Node->Balance == 1)
  189.         {
  190.           Parent->Balance = 0;
  191.           Node->Balance = 0;
  192.         }
  193.           else
  194.         {
  195.           Parent->Balance = -(Node->Left->Balance == 1);
  196.           Node->Balance = (Node->Left->Balance == -1);
  197.           Node->Left->Balance = 0;
  198.           Rotate_R (Tree, Node);
  199.         }
  200.           Rotate_L (Tree, Parent);
  201.           return NULL;
  202.         }
  203.     }
  204.     }
  205.   return NULL;
  206. }
  207.  
  208. /************************************************************************/
  209. /*                                                                      */
  210. /* Search a node                                                        */
  211. /* NULL for not found                                                   */
  212. /*                                                                      */
  213. /************************************************************************/
  214.  
  215. struct AVLNode *
  216. AVL_SearchNode (struct AVLTree *Tree, struct AVLNode *Node)
  217.  
  218. {
  219.   struct AVLNode *CurrentNode;
  220.   int CompareResult;
  221.  
  222.   CurrentNode = Tree->Root;
  223.   while (CurrentNode && (CompareResult = Tree->CompareNodes (Node, CurrentNode)))
  224.     {
  225.       if (CompareResult < 0)
  226.     {
  227.       CurrentNode = CurrentNode->Left;
  228.     }
  229.       else
  230.     {
  231.       CurrentNode = CurrentNode->Right;
  232.     }
  233.     }
  234.   return CurrentNode;
  235. }
  236.  
  237. /************************************************************************/
  238. /*                                                                      */
  239. /* Init the state info for a traversal.                                 */
  240. /*                                                                      */
  241. /************************************************************************/
  242.  
  243. void
  244. AVL_InitTraversal (struct AVLTree *Tree, struct AVLStateInfo *StateInfo)
  245.  
  246. {
  247.   StateInfo->FromNode = NULL;
  248.   StateInfo->CurrentNode = Tree->Root;
  249.   StateInfo->GoRight = FALSE;
  250. }
  251.  
  252. /************************************************************************/
  253. /*                                                                      */
  254. /* Do an inorder traversal of a tree.                                   */
  255. /*                                                                      */
  256. /************************************************************************/
  257.  
  258. struct AVLNode *
  259. AVL_InOrder (struct AVLStateInfo *StateInfo)
  260.  
  261. {
  262.   if (StateInfo->GoRight)
  263.     {
  264.       StateInfo->FromNode = StateInfo->CurrentNode;
  265.       if (StateInfo->CurrentNode->Right)
  266.     {
  267.       StateInfo->CurrentNode = StateInfo->CurrentNode->Right;
  268.     }
  269.       else
  270.     {
  271.       StateInfo->CurrentNode = StateInfo->CurrentNode->Parent;
  272.     }
  273.     }
  274.  
  275.   while (StateInfo->CurrentNode)
  276.     {
  277.       if (StateInfo->FromNode == StateInfo->CurrentNode->Parent)
  278.     {
  279.       if (StateInfo->CurrentNode->Left)
  280.         {
  281.           StateInfo->FromNode = StateInfo->CurrentNode;
  282.           StateInfo->CurrentNode = StateInfo->CurrentNode->Left;
  283.         }
  284.       else
  285.         {
  286.           StateInfo->GoRight = TRUE;
  287.           return StateInfo->CurrentNode;
  288.         }
  289.     }
  290.       else if (StateInfo->FromNode == StateInfo->CurrentNode->Left)
  291.     {
  292.       StateInfo->GoRight = TRUE;
  293.       return StateInfo->CurrentNode;
  294.     }
  295.       else
  296.     /* FromNode == CurrentNode->Right */
  297.     {
  298.       StateInfo->FromNode = StateInfo->CurrentNode;
  299.       StateInfo->CurrentNode = StateInfo->CurrentNode->Parent;
  300.     }
  301.     }
  302.   return NULL;
  303. }
  304.